#include <iostream>

//冒泡排序
void BubbleSort(int *a, int size)//传入指针地址及长度
{
    for(int i = 0; i < size - 1; i++)//最差情况下的大循环
    {
        int flag = 0;
        for(int j = 0; j < size - 1 - i; j++)//比较的次数，因为一次大循环会放一个最大的数在后面，就不用继续比较了
        {
            if(a[j] > a[j + 1])//判断大小，之后互换位置
            {
                flag = 1;
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        //用来减少大循环的次数，效率更高
        if(flag == 0)//说明已经没有数进行互换
        {
            break;//直接跳出for循环
        }
    }
}

//插入排序：用于已经有序的序列，插入新的数字
void InsertSort(int *a, int size)
{
    for(int i = 1; i < size; i++)//从右往左比，i最小为1和0比
    {
        int j = i;
        int temp = a[i];
        for(;j > 0; j--)//内循环，j一定大于0
        {
            if(temp < a[j - 1])
            {
                a[j] = a[j - 1];
            }
            else
            {
                break;//跳出循环
            }          
        }
        a[j] = temp;
    }
}

//选择排序
void SelectSort(int* a, int size)
{
    for(int i = 0; i < size - 1; i++)
    {
        int min = i;//默认开始位置标记为min
        for(int j = i + 1; j < size; j ++)
        {
            if(a[j] < a[min])
            {
                min = j;//把min的标签给j
            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

//双指针排序
void SelectSort2(int *a, int size)
{
    int left = 0;
    int right = size - 1;
    for(;left < right; left++, right--)//循环直到left = right
    {
        int min = left;//小的放左边
        int max = right;//大的放右边
        for(int i = left; i < right; i++)
        {
            if(a[i] < a[min])//比最小的还小
                min = i;
            if(a[i] > a[max])//比最大的还大
                max = i;
        }
        std::swap(a[left],a[min]);
        if(max == left)
        {
            max = min;//当最大值在最左边，则和min交换下标
        }
        std::swap(a[right],a[max]);
    }
}

int main()
{
    int a[] = {7,9,6,8,2,3,4,1,5,10};
    // BubbleSort(a,sizeof(a)/sizeof(a[0]));
    //InsertSort(a,sizeof(a)/sizeof(a[0]));
    SelectSort(a,sizeof(a)/sizeof(a[0]));
    for(int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    return 0;
}